πŸ‘©β€πŸ’» 20922. κ²ΉμΉ˜λŠ” 건 μ‹«μ–΄

@Seongukbaek Posted May 28, 2022 Β· Updated May 28, 2022 Β· 2 min read

문제

BOJ - κ²ΉμΉ˜λŠ” 건 μ‹«μ–΄

πŸ“ Logic

while(s <= e) { if (e == numbers.length) { max = Math.max(max, e - s); break; } int n = numbers[e]; if (numMap.containsKey(n)) { if (numMap.get(n) == K) { max = Math.max(max, e - s); int count = numMap.get(numbers[s]) - 1; if (count == 0) numMap.remove(numbers[s]); else numMap.put(numbers[s], count); s++; } else { numMap.put(n, numMap.getOrDefault(n, 0) + 1); e++; } } else { numMap.put(n, 1); e++; } }
  • Map 을 μ΄μš©ν•΄ ν•΄λ‹Ή μˆ«μžκ°€ λ¬Έμžμ—΄μ— λ‚˜νƒ€λ‚œ 횟수λ₯Ό μ €μž₯ν•œλ‹€.
  • 이미 K κ°œκ°€ λ¬Έμžμ—΄μ— λ“€μ–΄μžˆλ‹€λ©΄, s 지점에 μžˆλŠ” μˆ«μžλΆ€ν„° 1κ°œμ”© μ€„μ—¬λ‚˜κ°„λ‹€.

    • Map μ—μ„œ -1ν•˜κ³ , s λ₯Ό 1μ”© μ¦κ°€μ‹œν‚¨λ‹€.
  • 아직 K κ°œκ°€ λ¬Έμžμ—΄μ— λ“€μ–΄μžˆμ§€ μ•Šλ‹€λ©΄, λ‚˜νƒ€λ‚œ 횟수λ₯Ό 1μ”© μ¦κ°€μ‹œν‚¨λ‹€.
  • 아직 λ¬Έμžμ—΄μ— λ“€μ–΄μžˆμ§€ μ•Šμ€ κ²½μš°μ™€ K κ°œκ°€ λ¬Έμžμ—΄μ— λ“€μ–΄μžˆμ§€ μ•Šμ€ 경우만 e λ₯Ό μ¦κ°€μ‹œμΌœ λ‹€μŒ 숫자λ₯Ό 확인할 수 μžˆλ„λ‘ ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); int N = info[0]; int K = info[1]; int s = 0; int e = 0; int max = 0; Map<Integer, Integer> numMap = new HashMap<>(); int[] numbers = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); while(s <= e) { if (e == numbers.length) { max = Math.max(max, e - s); break; } int n = numbers[e]; if (numMap.containsKey(n)) { if (numMap.get(n) == K) { max = Math.max(max, e - s); int count = numMap.get(numbers[s]) - 1; if (count == 0) numMap.remove(numbers[s]); else numMap.put(numbers[s], count); s++; } else { numMap.put(n, numMap.getOrDefault(n, 0) + 1); e++; } } else { numMap.put(n, 1); e++; } } System.out.println(max); } }

✏️ Review

  • 투 포인터λ₯Ό μ‚¬μš©ν•˜λŠ” 문제 쀑 κ·Έλ‚˜λ§ˆ μ‰¬μ›Œλ³΄μ—¬μ„œ ν‘Ό 문제
  • s 와 e 에 λŒ€ν•œ 착각으둜 μ‹œκ°„μ΄ μ’€ κ±Έλ Έλ‹€...

πŸ“• 좜처

Baekjoon : https://www.acmicpc.net/problem/17779

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€